1. Field of the Invention
The present invention relates to communication networks and, more particularly, to a method and apparatus for achieving transparent redundancy at a hierarchical boundary in a communication network.
2. Description of the Related Art
Data communication networks may include various computers, servers, nodes, routers, switches, hubs, proxies, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network devices.” Data is communicated through the data communication network by passing data packets (or data cells or segments) between the network devices by utilizing one or more communication links. A particular packet may be handled by multiple network devices and cross multiple communication links as it travels between its source and its destination over the network.
The various network devices on the communications network communicate with each other using predefined sets of rules, referred to herein as protocols. Different protocols are used to govern different aspects of the communication, such as how signals should be formed for transmission between network devices, various aspects of what the data packets should look like, and how packets should be handled by the network devices. A group of network devices communicating via a given protocol or instantiation of a protocol will be referred to herein as a “domain.” Depending on how the network has been set up, a given packet of data may pass through multiple domains as it makes its way through the communications network. The interface between domains will be referred to herein as a hierarchical boundary in the communication network. A network device sitting on a hierarchical boundary will be referred to as a boundary network device.
Two protocols of particular interest herein are Multiprotocol Label Switching (MPLS) and Broadcast Multiple Access (BMA) protocols, such as Ethernet. MPLS is a protocol that is designed to set up paths through a packet network by applying labels to packets on a particular flow. When packets enter a MPLS-based network, Label Edge Routers (LERs) give them a label (identifier). Packets are classified into groups known as forwarding equivalence classes (FECs) which are packets that will get a common treatment by the MPLS network. The FEC may be expressed as forwarding rules derived from the routing table entry (i.e., destination, bandwidth, delay, and other metrics), and may also refer to the IP header field (source IP address), Layer 4 socket number information, differentiated service field, etc. The FEC is mapped to a corresponding LSP which instantiates the correct handling by the network. It is locally instantiated as a label “binding” on a particular interface. Once this classification into FECs is complete and the FEC to LSP binding obtained, the payload packets are forwarded on the corresponding Labeled Switch Paths (LSPs). With these LSPs, network operators can divert and route traffic based on data-stream type and Internet-access customer.
A BMA protocol such as Ethernet, by contrast, specifies that a network device is to send a packet to any nodes on the network in the domain without discriminating as to whether the adjacent nodes need to receive the packet. Within a shared Ethernet subnet, all network elements will receive broadcast traffic, and the receiver uses the embedded addressing (known as media access control or MAC addresses) to determine whether to accept or discard the packet.
Within the OSI networking model, Ethernet is considered to be a link layer protocol. Most proponents of MPLS do not consider MPLS as a unique layer within this model, however it is useful to similarly consider it as a link layer protocol as it implements a unique forwarding plane. As described in greater detail in IETF RFC 3032, the content of which is hereby incorporated herein by reference, Ethernet may carry MPLS via the use of encapsulation/overlay techniques. Likewise, as described in greater detail in http://www.ietf.org/internet-drafts/draft-martini-12circuit-encap-mpls-04.txt, the content of which is hereby incorporated herein by reference, MPLS may carry Ethernet. Further, MPLS implements arbitrary hierarchy, that is to say that MPLS protocol data units (PDUs) can carry MPLS PDUs whereby layers recursively stack. This introduces a number of challenges in creating a highly reliable network, as hierarchical boundaries are normally single points of failure in the network, and an arbitrary number of hierarchical boundaries may be traversed by a given end-to-end path across the network.
FIGS. 1-3 illustrate several examples of networks in which a hierarchical boundary 10 exists between two domains. In the example illustrated in FIG. 1, a provider edge network device 16 sits at the hierarchical boundary 10 between a broadcast domain 12 and a MPLS domain 14. In this example, customer traffic on a customer's local area network (not shown) is transmitted from a customer edge network device 18 through the broadcast domain 12 to the provider edge network device 16. The provider edge network device 16 aggregates traffic from various customers and packages it for transmission over the network forming the MPLS domain 14.
In the example illustrated in FIG. 2, a core provider edge network device (Core PE 20) sits at a hierarchical boundary 10 between the broadcast domain 12 and the MPLS domain 14. In this example, customer traffic on a customer's local area network (not shown) is transmitted from the customer edge network device 18 to an edge provider edge network device (Edge PE 22). The Edge PE network device 22 aggregates customer traffic and sends it over the network forming the broadcast domain 12 to the Core PE network device 20. The Core PE network device 20 then transmits the incoming traffic, as necessary, over the network forming the MPLS domain 14.
In the example illustrated in FIG. 3, a boundary network device 24 sits at the hierarchical boundary 10 between MPLS domain A (14A) and MPLS domain B (14B). Hierarchical boundaries of this nature are typically formed where multiple layers of MPLS labels are applied to a given traffic flow, for example, where a second MPLS label is attached to packets in an existing MPLS flow for transmission across another network or another part of the network. Many other network topographies may be envisioned employing hierarchical boundaries between a broadcast domain and a MPLS domain, or between multiple MPLS domains, and the invention, as described below, is not limited to these few examples of hierarchical boundaries in communications networks.
As data networks have grown in complexity and speed, the network devices used in those networks have likewise increased in complexity and speed. Unfortunately, this complexity provides manifest opportunities for the network to fail. To increase reliability of the network, networks are designed such that in the event of a failure of a network device or link, an alternate network device or link may be used until a repair can be made to the failed element. This notion will be referred to herein as “redundancy.” Where the repair works around the failure by selecting an alternate network device or link, the repair will be referred to as a local repair. Where the repair establishes an entirely new end-to-end path through the domain, the repair will be referred to as global repair.
As services offered over networks become increasingly complex, for example layer 2 and layer 3 virtual private networks (VPNs) are deployed, and virtual private LAN segment (VPLS) services are made available, redundancy becomes increasingly important, and also increasingly difficult. Specifically, the redundant network devices must share information as to the types of tunnels, etc. that are being set up to provide these services, so that in the event of failure of one network device another network device can continue to offer these specialized services. Ethernet networks have mechanisms to permit redundant domain interconnect (e.g. VRRP). MPLS provides for both path repair and segment repair mechanisms (known as global and local repair respectively) Global repair mechanisms will not be further considered as use of hierarchy simply results in bandwidth explosion. For local repair, additional backup paths are set up to circumvent any point of failure between the path egress and ingress, with the ingress and egress being points of failure. So if there are ‘n’ points of failure, there will be ‘n’ backup paths.
Unfortunately, to date there has been no satisfactory way to extend the local repair mechanisms to provide transparent redundancy at a hierarchical boundary. Specifically, since the local repair mechanisms specify an alternate path around the broken network device or link, any attempt at repairing a boundary network device would necessarily result in traffic crossing the hierarchical boundary at a different point. Since there is no convenient or established way of coordinating this with the second domain, boundary network devices represent a single point of failure on the network.